import java.util.LinkedList;
import java.util.List;

public class Solution797 {
    static class Node{
        Node previous;
        int now;

        public Node(Node previous, int now) {
            this.previous = previous;
            this.now = now;
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        LinkedList<Node> linkedList=new LinkedList();
        List<List<Integer>> ans=new LinkedList();
        Node node= new Node(null, 0);
        linkedList.addLast(node);
        while (!linkedList.isEmpty()){
            Node node1=linkedList.getFirst();
            if (node1.now==graph.length-1){
                LinkedList<Integer> result=new LinkedList();
                Node temp=node1;
                while (temp!=null){
                    result.addFirst(temp.now);
                    temp=temp.previous;
                }
                ans.add(result);
            }
            for (int i=0;i<graph[node1.now].length;i++){
                linkedList.addLast(new Node(node1, graph[node1.now][i]));
            }
            linkedList.removeFirst();
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution797().allPathsSourceTarget(new int[][]{{1,2},{3},{3},{}}));
    }
}

